package com.linzm.leetcode.primary.exercises1_20230114;

import java.util.*;
import java.util.stream.Collectors;

/**
 * @Author zimingl
 * @Date 2023/1/15 21:57
 * @Description: 有序数组中出现次数超过25%的元素
 */
public class Demo25_1287 {
    /**
     * 输入：arr = [1,2,2,6,6,6,6,7,10]
     * 输出：6
     */
    public static void main(String[] args) {
//        int[] arr = {1,2,3,3};
        int[] arr = {1, 2, 2, 6, 6, 6, 6, 10};
        Demo25_1287 demo25_1287 = new Demo25_1287();
        int num = demo25_1287.findSpecialInteger2(arr);
        System.out.println(num);
    }

    private int findSpecialInteger(int[] arr) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < arr.length; i++) {
            int count = map.getOrDefault(arr[i], 0) + 1;
            map.put(arr[i], count);
        }
        List<Map.Entry<Integer, Integer>> collect = map.entrySet().stream()
                .sorted((e1, e2) -> e2.getValue() - e1.getValue())
                .collect(Collectors.toList());
        Integer value = collect.get(0).getValue();
        if (value / arr.length >= 1 / 4) {
            return collect.get(0).getKey();
        }
        return -1;
    }

    /**
     * 1/4 的区间
     * @param arr arr
     * @return arr[i]
     */
    private int findSpecialInteger2(int[] arr) {
        for (int i = 0, len = arr.length / 4; i < arr.length - len; i++){
            if (arr[i] == arr[i + len]) {
                return arr[i];
            }
        }
        return -1 ;
    }
}
